Randomized algorithms for distributed computation of principal component analysis and singular value decomposition

摘要

Randomized algorithms provide solutions to two ubiquitous problems: (1) thedistributed calculation of a principal component analysis or singular valuedecomposition of a highly rectangular matrix, and (2) the distributedcalculation of a low-rank approximation (in the form of a singular valuedecomposition) to an arbitrary matrix. Carefully honed algorithms yield resultsthat are uniformly superior to those of the stock, deterministicimplementations in Spark (the popular platform for distributed computation); inparticular, whereas the stock software will without warning return leftsingular vectors that are far from numerically orthonormal, a significantlyburnished randomized implementation generates left singular vectors that arenumerically orthonormal to nearly the machine precision.